A disk drive receives multiple commands to execute essentially random disk address input/output (I/O) transfers. In other words, the I/O commands require data to be written or read at various locations throughout the disk drive. When the commands arrive faster than they can be executed, they accumulate in a queue. By recognizing that I/O commands need not be executed in the order received, I/O throughput may be increased by minimizing latency between transfers, i.e., minimize the interval between times of actually reading or writing data relative to the disk media. Execution of commands in an order different from that received is called a command queue reordering procedure.
Various methods have been used before in reordering a command queue. One method termed "Shortest Seek Time First," or SSTF, reorders the commands in the queue so that the command which has the shortest seek time with respect to the command being executed is next executed. Another method called the sequential cylinder access number (SCAN) method reorders the commands in the queue such that they are processed in cylinder number order, ensuring that I/O transfers near the edges of the disk are processed. These and other queuing methods based on the cylinder number of the I/O transfers are described and analyzed in Teorey and Pinkerton, "A comparative Analysis of Disk Scheduling Policies," Comm. ACM, Vol. 15, No. 3, March 1972, pp. 177-184, in Geist and Daniel, "A continuum of Disk Scheduling Algorithms," ACM Trans. on Computer Systems, Vol. 5, No. 1, February, 1987, pp. 77-92, and in Denning, "Effects of Scheduling on File Memory Operations," American Federation of Information Processing Societies (AFIPS) Joint Computer Conference Proceedings, Vol. 30, 1967, pp. 9-21.
U.S. Pat. No. 4,583,166, U.S. Pat. No. 5,140,683, and U.S. Pat. No. 4,232,365 also describe various queue reordering techniques.
Co-pending application Ser. No. 08/149,982 filed on Nov. 10, 1993, by the present inventor and entitled: ROTATIONAL LATENCY QUEUE REORDERING, and assigned in common to the assignee of the present application, describes a queue reordering technique taking into account both seek time and rotational latency in determining the time delay between executing commands. In the queue reordering process, a simple, step wise, shortest time first algorithm promotes a selected command to next execute. First, the algorithm initializes variables for the current pass of reordering. Second, a series of latency computation steps for each command in the queue provides a measure of latency for each command with respect to the head-of-queue command, i.e., the command presently under execution. Third, a scan along the command queue selects the least-latency command and promotes such command to a position immediately following the head-of-queue command, i.e., following the command currently under execution. The above first, second, and third procedures are completed during execution of the head-of-queue command. At completion, the head-of-queue command is deleted from the command queue, thereby making the just promoted least-latency command next to execute. Upon initiation of such execution, the algorithm repeats for another pass of the above noted step procedures for command queue reordering.
Thus, a variety of algorithms exist for scheduling I/O commands in a command queue. For expository convenience, the present application will refer to the command queue reordering algorithm of U.S. patent application Ser. No. 08/149,982, but need not be limited to such context of use. Accordingly, the disclosure of my co-pending of U.S. patent application Ser. No. 08/149,982 is incorporated herein fully by reference thereto.
Any queue reordering scheme must address data hazards in handling I/O commands with overlapping ranges of logical block addresses. For example, consider two I/O commands sent to the disk drive and having overlapping ranges of logical block addresses (LBA). If either command is a write command, the order of execution of the two commands can affect data written to the disk or transferred to the host. This condition is termed a "data hazard." Data hazards include a write-write hazard and a read-write hazard. If both commands, even with overlapping ranges of logical addresses, are read commands, the order of execution does not matter as no data hazard exists, i.e., there are no read-read data hazards. Thus, if the command queue includes write commands, command dependencies must be recognized to avoid data hazards.
In FIG. 1A, consider logical block addresses A, B, and C each originally containing the data pattern "z". A write(A,B,x) command and a write (B,C,y) command are presented for execution. The write (A,B,x) command fills logical block addresses A and B with the data pattern "x", while the write (B,C,y) command fills the logical block addresses B and C with the data pattern "y." If the write (A,B,x) command is first executed, logical block addresses A, B, and C ultimately will have data patterns "x", "y", and "y" respectively. If, however, the write (B,C,y) command is first executed, the logical block addresses A, B, and C ultimately will contain data patterns "x", "x", and "y", respectively. This is an example of a write-write hazard.
In FIG. 1B next consider a read (A,B) command referencing logical block addresses A and B and a write (B,C,y) command referencing addresses B and C. Regardless of the order of execution, logical address B and C will ultimately contain the data pattern "y" and logical address A will contain its original data pattern "z." The data hazard arises with respect to data submitted to the requesting host. More particularly, when the read (A,B) command executes first, the host receives the original content of logical addresses A and B, i.e., the data patterns "z" and "z." If, however, the write (B,C,y) command is first executed, the host receives in response to the read (A,B) command the original data value content of logical address A, i.e. the data pattern "z", but erroneously receives the data pattern "y" for the logical address B. This is an example of a read-write hazard.
Accordingly, to avoid data hazards, I/O command queue reordering must account for such dependencies in any order of I/O command execution which differs from the order of presentation. Generally, each I/O command is executed in the order presented, and reordered only under conditions taking into account the I/O command's dependency relative to I/O commands with overlapping logical block addresses. Any reordered sequence of I/O commands is semantically correct only if its execution results in the same data being written to disk, or the same data being transferred to the host, which would have been written or transferred had the I/O commands been executed in the order of original presentation to the disk drive.
The task of comparing logical block address ranges and managing dependencies can incorporate substantial computational overhead into the disk drive control apparatus. Because interaction with the host and supervision over data transfers between the host and the selected disk data storage location(s) is interleaved with the I/O command queue reordering process, any reordering process must be executed in a timely fashion for appropriate interleaving amongst other high priority disk control activities. Generally, simple methods of command queue reordering require a high level of computational overhead when performing address overlap-checks to identify data hazards. To complete all latency computations and overlay checks in time, the number of candidates considered for command queue promotion may have to be limited, thereby restricting the search for least-latency to a subset of the present I/O command queue.
Excess computational overhead arises not so much with latency computation, but when a command selected for its desirable characteristic of least-latency is found to have a dependency on a more forward command in the queue and cannot be promoted to be next executed. A new candidate for promotion must be selected. This requires repeat execution of both the selection and the overlap checking procedures to find the next best least-latency command. As used herein, the term "n" represents the number of I/O commands in the command queue, and the term ".alpha." represents the number of dependencies in the queue. The number of repetitions required to obtain a command eligible for promotion within the command queue is .omicron.(.alpha.) on the average. For each repetition, the time required for scanning down the queue to find a least latency command is .omicron.(n), and the time required for a series of address overlap checks between the selected command and the commands in front of it in the queue is .omicron.(n) on the average. Therefore the complexity of the whole selection process is .omicron.(n)*.omicron.(.alpha.)=.omicron.(n*.alpha.) to find a least-latency command eligible for promotion.
This computational overhead is undesirable for the potential of the final selection step requiring too much processing time. Because queue reordering must be interleaved with disk and host transfer activity, a step in the queue reordering process having computational overhead of .omicron.(n*.alpha.) can cause undesirable delay in handling the more time-critical, higher priority host interaction activities.
One particularly burdensome aspect of the above noted simple method of incorporating a dependency check into the reordering algorithm is the number of comparisons required in address overlap checking. For consecutive passes of reordering, every time a command is proposed for promotion, a series of address overlap checks must be executed for that command, even if it was earlier proposed for promotion, because previous dependencies for that command may have been removed as more forward commands exit the queue.
Accordingly, a command queue reordering algorithm must actively maintain dependency information in command execution sequence. Such algorithms are desirably not computationally burdensome to the point that more vital or higher priority activities are degraded, i.e., interaction with a host slowed. The subject matter of the present invention provides such an I/O command queue reordering algorithm which takes into account command dependencies, but does not impose an unacceptable computational overhead otherwise interfering with host-disk interaction: i.e., interference with accepting new commands and writing data, and delivering the results of read operations to the host.